SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Flow network</title>

</head>

Flow network

</h1>

</header>

In <a href="Graph_theory" title="Graph theory">graph theory</a>, a flow network (also known as a transportation network) is a <a href="Directed_graph" title="Directed graph">directed graph</a> where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in <a href="Operations_research" title="Operations research">operations research</a>, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A flow network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. As such, efficient algorithms for solving network flows can also be applied to solve problems that can be reduced to a flow network, including survey design, airline scheduling, <a href="Image_segmentation" title="Image segmentation">image segmentation</a>, and the <a href="Matching_(graph_theory)" title="Matching (graph theory)">matching problem</a>.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

A network is a directed graph G = (V, E) with a non-negative capacity <a href="Function_(mathematics)" title="Function (mathematics)">function</a> c for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). <a href="Without_loss_of_generality" title="Without loss of generality">Without loss of generality</a>, we may assume that if (u, v) ∈ E, then (v, u) is also a member of E. Additionally, if (v, u) ∉ E then we may add (v, u) to E and then set the c(v, u) = 0.

If two nodes in G are distinguished – one as the source s and the other as the sink t – then (G, c, s, t) is called a flow network.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Flows">Flows</h2></div>

Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The amount of flow between two nodes is used to represent the net amount of units being transferred from one node to the other.

The excess function xf : V → ℝ represents the net flow entering a given node u (i.e. the sum of the flows entering u) and is defined by<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{f}(u)=\sum _{w\in V}f(w,u)-\sum _{w\in V}f(u,w).}">

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{f}(u)=\sum _{w\in V}f(w,u)-\sum _{w\in V}f(u,w).}</annotation>

</semantics>

</math>A node u is said to be active if xf (u) > 0 (i.e. the node u consumes flow), deficient if xf (u) < 0 (i.e. the node u produces flow), or conserving if xf (u) = 0. In flow networks, the source s is deficient, and the sink t is active.

Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.

<dl><dd>A pseudo-flow is a function f of each edge in the network that satisfies the following two constraints for all nodes u and v:

<ul><li>Skew symmetry constraint: The flow on an arc from u to v is equivalent to the negation of the flow on the arc from v to u, that is: f (u, v) = −f (v, u). The sign of the flow indicates the flow's direction.</li>

<li>Capacity constraint: An arc's flow cannot exceed its capacity, that is: f (u, v) ≤ c(u, v).</li></ul></dd>

<dd>A pre-flow is a pseudo-flow that, for all v ∈ V \{s}, satisfies the additional constraint:

<ul><li>Non-deficient flows: The net flow entering the node v is non-negative, except for the source, which "produces" flow. That is: xf (v) ≥ 0 for all v ∈ V \{s}.</li></ul></dd>

<dd>A feasible flow, or just a flow, is a pseudo-flow that, for all v ∈ V \{s, t}, satisfies the additional constraint:

<ul><li>Flow conservation constraint: The total net flow entering a node v is zero for all nodes in the network except the source s and the sink t, that is: xf (v) = 0 for all v ∈ V \{s, t}. In other words, for all nodes in the network except the source s and the sink t, the total sum of the incoming flow of a node is equal to its outgoing flow (i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)}">

</mrow>

</munder>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)}</annotation>

</semantics>

</math><img src="./4ce270f3123cdccd782921115af43d6b7bc4a89c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:28.271ex; height:6.009ex;" alt="{\displaystyle \sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)}" loading="lazy">, for each vertex v ∈ V \{s, t}).</li></ul></dd></dl>

The value |f| of a feasible flow f for a network, is the net flow into the sink t of the flow network, that is: |f| = xf (t). Note, the flow value in a network is also equal to the total outgoing flow of source s, that is: |f| = −xf (s). Also, if we define A as a set of nodes in G such that s ∈ A and t ∉ A, the flow value is equal to the total net flow going out of A (i.e. |f| = f out(A) − f in(A)).<a href="#cite_note-:0-2">[2]</a> The flow value in a network is the total amount of flow from s to t.

<div class="mw-heading mw-heading2"><h2 id="Concepts_useful_to_flow_problems">Concepts useful to flow problems</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Flow_decomposition">Flow decomposition</h3></div>

Flow decomposition<a href="#cite_note-3">[3]</a> is a process of breaking down a given flow into a collection of path flows and cycle flows. Every flow through a network can be decomposed into one or more paths and corresponding quantities, such that each edge in the flow equals the sum of all quantities of paths that pass through it. Flow decomposition is a powerful tool in optimization problems to maximize or minimize specific flow parameters.

<div class="mw-heading mw-heading3"><h3 id="Adding_arcs_and_flows">Adding arcs and flows</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

We do not use multiple arcs within a network because we can combine those arcs into a single arc. To combine two arcs into a single arc, we add their capacities and their flow values, and assign those to the new arc:

<ul><li>Given any two nodes u and v, having two arcs from u to v with capacities c1(u,v) and c2(u,v) respectively is equivalent to considering only a single arc from u to v with a capacity equal to c1(u,v)+c2(u,v).</li>

<li>Given any two nodes u and v, having two arcs from u to v with pseudo-flows f1(u,v) and f2(u,v) respectively is equivalent to considering only a single arc from u to v with a pseudo-flow equal to f1(u,v)+f2(u,v).</li></ul>

Along with the other constraints, the skew symmetry constraint must be remembered during this step to maintain the direction of the original pseudo-flow arc. Adding flow to an arc is the same as adding an arc with the capacity of zero.

<div class="mw-heading mw-heading3"><h3 id="Residuals">Residuals</h3></div>

The residual capacity of an arc e with respect to a pseudo-flow f is denoted cf, and it is the difference between the arc's capacity and its flow. That is, cf (e) = c(e) − f(e). From this we can construct a residual network, denoted Gf (V, Ef), with a capacity function cf which models the amount of available capacity on the set of arcs in G = (V, E). More specifically, capacity function cf of each arc (u, v) in the residual network represents the amount of flow which can be transferred from u to v given the current state of the flow within the network.

This concept is used in <a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson algorithm</a> which computes the <a href="Maximum_flow" class="mw-redirect" title="Maximum flow">maximum flow</a> in a flow network.

Note that there can be an unsaturated path (a path with available capacity) from u to v in the residual network, even though there is no such path from u to v in the original network. Since flows in opposite directions cancel out, decreasing the flow from v to u is the same as increasing the flow from u to v.

<div class="mw-heading mw-heading3"><h3 id="Augmenting_paths">Augmenting paths</h3></div>

An augmenting path is a path (u1, u2, ..., uk) in the residual network, where u1 = s, uk = t, and for all ui, ui + 1 (cf (ui, ui + 1) > 0) (1 ≤ i < k). More simply, an augmenting path is an available flow path from the source to the sink. A network is at <a href="Maximum_flow" class="mw-redirect" title="Maximum flow">maximum flow</a> if and only if there is no augmenting path in the residual network Gf.

The bottleneck is the minimum residual capacity of all the edges in a given augmenting path.<a href="#cite_note-:0-2">[2]</a> See example explained in the "Example" section of this article. The flow network is at maximum flow if and only if it has a bottleneck with a value equal to zero. If any augmenting path exists, its bottleneck weight will be greater than 0. In other words, if there is a bottleneck value greater than 0, then there is an augmenting path from the source to the sink. However, we know that if there is any augmenting path, then the network is not at maximum flow, which in turn means that, if there is a bottleneck value greater than 0, then the network is not at maximum flow.

The term "augmenting the flow" for an augmenting path means updating the flow f of each arc in this augmenting path to equal the capacity c of the bottleneck. Augmenting the flow corresponds to pushing additional flow along the augmenting path until there is no remaining available residual capacity in the bottleneck.

<div class="mw-heading mw-heading3"><h3 id="Multiple_sources_and/or_sinks">Multiple sources and/or sinks</h3></div>

Sometimes, when modeling a network with more than one source, a supersource is introduced to the graph.<a href="#cite_note-4">[4]</a> This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

In Figure 1 you see a flow network with source labeled s, sink t, and four additional nodes. The flow and capacity is denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f/c}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f/c}</annotation>

</semantics>

</math><img src="./fb831cd04ec8b60f900a75341088eb25ac2f255a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.448ex; height:2.843ex;" alt="{\displaystyle f/c}" loading="lazy">. Notice how the network upholds the capacity constraint and flow conservation constraint. The total amount of flow from s to t is 5, which can be easily seen from the fact that the total outgoing flow from s is 5, which is also the incoming flow to t. By the skew symmetry constraint, from c to a is -2 because the flow from a to c is 2.

In Figure 2 you see the residual network for the same given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero in Figure 1, for example for the edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (d,c)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (d,c)}</annotation>

</semantics>

</math><img src="./67dbe3343879ab3dd75427ddd90bc98b36131912.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.066ex; height:2.843ex;" alt="{\displaystyle (d,c)}" loading="lazy">. This network is not at <a href="Maximum_flow" class="mw-redirect" title="Maximum flow">maximum flow</a>. There is available capacity along the paths <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (s,a,c,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s,a,c,t)}</annotation>

</semantics>

</math><img src="./757b09210ecacb5d69a15b75712980894025c804.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.078ex; height:2.843ex;" alt="{\displaystyle (s,a,c,t)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (s,a,b,d,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s,a,b,d,t)}</annotation>

</semantics>

</math><img src="./ded7bfb888df6e3d7e5eb6ce8163a7a575bdc705.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.318ex; height:2.843ex;" alt="{\displaystyle (s,a,b,d,t)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (s,a,b,d,c,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s,a,b,d,c,t)}</annotation>

</semantics>

</math><img src="./0ee0e5e49b941d74086ee160cf2f9b742cd13e9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.359ex; height:2.843ex;" alt="{\displaystyle (s,a,b,d,c,t)}" loading="lazy">, which are then the augmenting paths.

The bottleneck of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (s,a,c,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s,a,c,t)}</annotation>

</semantics>

</math><img src="./757b09210ecacb5d69a15b75712980894025c804.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.078ex; height:2.843ex;" alt="{\displaystyle (s,a,c,t)}" loading="lazy"> path is equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))}</annotation>

</semantics>

</math><img src="./e0367dfec282fd04b8be37d1e96473f062754325.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:52.996ex; height:2.843ex;" alt="{\displaystyle \min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))}</annotation>

</semantics>

</math><img src="./28aa2e2272e7b92cda85f91311739c49ea728e8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:31.568ex; height:3.009ex;" alt="{\displaystyle =\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =\min(5-3,3-2,2-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =\min(5-3,3-2,2-1)}</annotation>

</semantics>

</math><img src="./8a710c721b6ca505688bcc5962c8ecc3846f27d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.702ex; height:2.843ex;" alt="{\displaystyle =\min(5-3,3-2,2-1)}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =\min(2,1,1)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =\min(2,1,1)=1}</annotation>

</semantics>

</math><img src="./a2604793b987ce3896d4715d8546c27a85d102e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.954ex; height:2.843ex;" alt="{\displaystyle =\min(2,1,1)=1}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Pipe_network_analysis" title="Pipe network analysis">Pipe network analysis</a></div>

Picture a series of water pipes, fitting into a network. Each pipe is of a certain diameter, so it can only maintain a flow of a certain amount of water. Anywhere that pipes meet, the total amount of water coming into that junction must be equal to the amount going out, otherwise we would quickly run out of water, or we would have a buildup of water. We have a water inlet, which is the source, and an outlet, the sink. A flow would then be one possible way for water to get from source to sink so that the total amount of water coming out of the outlet is consistent. Intuitively, the total flow of a network is the rate at which water comes out of the outlet.

Flows can pertain to people or material over transportation networks, or to electricity over <a href="Electrical_distribution" class="mw-redirect" title="Electrical distribution">electrical distribution</a> systems. For any such physical network, the flow coming into any intermediate node needs to equal the flow going out of that node. This conservation constraint is equivalent to <a href="Kirchhoff's_current_law" class="mw-redirect" title="Kirchhoff's current law">Kirchhoff's current law</a>.

Flow networks also find applications in <a href="Ecology" title="Ecology">ecology</a>: flow networks arise naturally when considering the flow of nutrients and energy between different organisms in a <a href="Food_web" title="Food web">food web</a>. The mathematical problems associated with such networks are quite different from those that arise in networks of fluid or traffic flow. The field of ecosystem network analysis, developed by <a href="Robert_Ulanowicz" title="Robert Ulanowicz">Robert Ulanowicz</a> and others, involves using concepts from <a href="Information_theory" title="Information theory">information theory</a> and <a href="Thermodynamics" title="Thermodynamics">thermodynamics</a> to study the evolution of these networks over time.

<div class="mw-heading mw-heading2"><h2 id="Classifying_flow_problems">Classifying flow problems</h2></div>

The simplest and most common problem using flow networks is to find what is called the <a href="Maximum_flow" class="mw-redirect" title="Maximum flow">maximum flow</a>, which provides the largest possible total flow from the source to the sink in a given graph. There are many other problems which can be solved using max flow algorithms, if they are appropriately modeled as flow networks, such as <a href="Bipartite_matching" class="mw-redirect" title="Bipartite matching">bipartite matching</a>, the <a href="Assignment_problem" title="Assignment problem">assignment problem</a> and the <a href="Transportation_problem" class="mw-redirect" title="Transportation problem">transportation problem</a>. Maximum flow problems can be solved in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> with various algorithms (see table). The <a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">max-flow min-cut theorem</a> states that finding a maximal network flow is equivalent to finding a <a href="Cut_(graph_theory)" title="Cut (graph theory)">cut</a> of minimum capacity that separates the source and the sink, where a cut is the division of vertices such that the source is in one division and the sink is in another.

<caption>Well-known algorithms for the Maximum Flow Problem

</caption>

<th>Inventor(s)</th>

<th>Time complexity (with n nodes and m arcs)

</th></tr>

<tr>

<td><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic's algorithm</a></td>

<td>O(mn2)

</td></tr>

<tr>

<td><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp algorithm</a></td>

<td>O(m2n)

</td></tr>

<tr>

<td>MPM (Malhotra, Pramodh-Kumar, and Maheshwari) algorithm<a href="#cite_note-6">[6]</a>

</td>

<td>O(n3)

</td></tr>

<tr>

<td><a href="Push%E2%80%93relabel_algorithm" class="mw-redirect" title="Push–relabel algorithm">Push–relabel algorithm</a> (<a href="Andrew_V._Goldberg" title="Andrew V. Goldberg">Goldberg</a> & <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan</a>)</td>

<td>O(n2m)

</td></tr>

<tr>

<td><a href="James_B._Orlin" title="James B. Orlin">James B. Orlin</a><a href="#cite_note-7">[7]</a></td>

<td>O(mn)

</td></tr>

<tr>

<td>Li Chen, Rasmus Kyng, Yang P. Liu,

Richard Peng, Maximilian Probst Gutenberg,

Sushant Sachdeva

</td>

<td>2022

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m^{1+o(1)})}</annotation>

</semantics>

</math><img src="./970488e3b6bcc7a94e78a40fad563a8683e028b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.854ex; height:3.343ex;" alt="{\displaystyle O(m^{1+o(1)})}" loading="lazy">

</td></tr></tbody></table>

In a <a href="Multi-commodity_flow_problem" title="Multi-commodity flow problem">multi-commodity flow problem</a>, you have multiple sources and sinks, and various "commodities" which are to flow from a given source to a given sink. This could be for example various goods that are produced at various factories, and are to be delivered to various given customers through the same transportation network.

In a <a href="Minimum_cost_flow_problem" class="mw-redirect" title="Minimum cost flow problem">minimum cost flow problem</a>, each edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u,v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u,v}</annotation>

</semantics>

</math><img src="./7e66f4b32a0181923cc1337a5634f38241e5c697.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.491ex; height:2.009ex;" alt="{\displaystyle u,v}" loading="lazy"> has a given cost <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k(u,v)}</annotation>

</semantics>

</math><img src="./808ae4bfa206821f9086b1dcd7dc45a44ee90d8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.512ex; height:2.843ex;" alt="{\displaystyle k(u,v)}" loading="lazy">, and the cost of sending the flow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(u,v)}</annotation>

</semantics>

</math><img src="./8f6a108a1020838e47fa6d73a3b9e00d38197ebb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.579ex; height:2.843ex;" alt="{\displaystyle f(u,v)}" loading="lazy"> across the edge is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(u,v)\cdot k(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(u,v)\cdot k(u,v)}</annotation>

</semantics>

</math><img src="./2f9664a51f0432adc90da6dc32e2a20e3c349ce3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.77ex; height:2.843ex;" alt="{\displaystyle f(u,v)\cdot k(u,v)}" loading="lazy">. The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.

In a <a href="Circulation_problem" title="Circulation problem">circulation problem</a>, you have a lower bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell (u,v)}</annotation>

</semantics>

</math><img src="./c8bdff0f6342ee13c0d97f05f7b4509cd9d08fc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.27ex; height:2.843ex;" alt="{\displaystyle \ell (u,v)}" loading="lazy"> on the edges, in addition to the upper bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(u,v)}</annotation>

</semantics>

</math><img src="./3af127906713b7741d8b0562429672f686b449b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.307ex; height:2.843ex;" alt="{\displaystyle c(u,v)}" loading="lazy">. Each edge also has a cost. Often, flow conservation holds for all nodes in a circulation problem, and there is a connection from the sink back to the source. In this way, you can dictate the total flow with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell (t,s)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell (t,s)}</annotation>

</semantics>

</math><img src="./46df1bdb0fdc5848262a77325baebf121738ed7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.743ex; height:2.843ex;" alt="{\displaystyle \ell (t,s)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(t,s)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(t,s)}</annotation>

</semantics>

</math><img src="./4d8aea67ab3b26f26e5eef46c57306177203773b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.78ex; height:2.843ex;" alt="{\displaystyle c(t,s)}" loading="lazy">. The flow circulates through the network, hence the name of the problem.

In a network with gains or generalized network each edge has a <a href="Gain_graph" title="Gain graph">gain</a>, a real number (not zero) such that, if the edge has gain g, and an amount x flows into the edge at its tail, then an amount gx flows out at the head.

In a source localization problem, an algorithm tries to identify the most likely source node of information diffusion through a partially observed network. This can be done in linear time for trees and cubic time for arbitrary networks and has applications ranging from tracking mobile phone users to identifying the originating source of disease outbreaks.<a href="#cite_note-8">[8]</a>

<ul><li><a href="Braess's_paradox" class="mw-redirect" title="Braess's paradox">Braess's paradox</a></li>

<li><a href="Centrality" title="Centrality">Centrality</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson algorithm</a></li>

<li><a href="Edmonds-Karp_algorithm" class="mw-redirect" title="Edmonds-Karp algorithm">Edmonds-Karp algorithm</a></li>

<li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic's algorithm</a></li>

<li><a href="Traffic_flow_(computer_networking)" title="Traffic flow (computer networking)">Traffic flow (computer networking)</a></li>

<li><a href="Flow_graph_(disambiguation)" class="mw-redirect mw-disambig" title="Flow graph (disambiguation)">Flow graph (disambiguation)</a></li>

<li><a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">Max-flow min-cut theorem</a></li>

<li><a href="Oriented_matroid" title="Oriented matroid">Oriented matroid</a></li>

<li><a href="Shortest_path_problem" title="Shortest path problem">Shortest path problem</a></li>

<li><a href="Nowhere-zero_flow" title="Nowhere-zero flow">Nowhere-zero flow</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKleinberg2011" class="citation book cs1">Kleinberg, Jon (2011). Algorithm design. Éva Tardos (2nd ed.). Boston, Mass.: Addison-Wesley. pp. 342, 346. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-213108-7</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/796210667">796210667</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFAhujaMagnantiOrlin1993" class="citation book cs1">Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network flows: theory, algorithms and applications. Englewood Cliffs (N. J.): Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-617549-0</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a>  This article incorporates <a href="Copyright_status_of_works_by_the_federal_government_of_the_United_States" title="Copyright status of works by the federal government of the United States">public domain material</a> from <cite id="CITEREFPaul_E._Black" class="citation cs1">Paul E. Black. <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/supersource.html">"Supersource"</a>. <a href="Dictionary_of_Algorithms_and_Data_Structures" class="mw-redirect" title="Dictionary of Algorithms and Data Structures">Dictionary of Algorithms and Data Structures</a>. <a href="NIST" class="mw-redirect" title="NIST">NIST</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a>  This article incorporates <a href="Copyright_status_of_works_by_the_federal_government_of_the_United_States" title="Copyright status of works by the federal government of the United States">public domain material</a> from <cite id="CITEREFPaul_E._Black" class="citation cs1">Paul E. Black. <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/supersink.html">"Supersink"</a>. <a href="Dictionary_of_Algorithms_and_Data_Structures" class="mw-redirect" title="Dictionary of Algorithms and Data Structures">Dictionary of Algorithms and Data Structures</a>. <a href="NIST" class="mw-redirect" title="NIST">NIST</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFMalhotraKumarMaheshwari1978" class="citation journal cs1">Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). <a rel="nofollow" class="external text" href="https://eprints.utas.edu.au/160/1/iplFlow.pdf">"An <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{3})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{3})}</annotation>

</semantics>

</math><img src="./04ad8b53a2cea864c6d746895cc7397971f72912.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.718ex; height:3.343ex;" alt="{\displaystyle O(|V|^{3})}" loading="lazy"> algorithm for finding maximum flows in networks"</a> (PDF). Information Processing Letters. 7 (6): 277–278. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2878%2990016-9">10.1016/0020-0190(78)90016-9</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210418071844/https://eprints.utas.edu.au/160/1/iplFlow.pdf">Archived</a> (PDF) from the original on 2021-04-18. Retrieved 2019-07-11.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFOrlin2013" class="citation book cs1">Orlin, James B. (2013-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/2488608.2488705">"Max flows in O(nm) time, or better"</a>. Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. STOC '13. Palo Alto, California, USA: Association for Computing Machinery. pp. 765–774. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2488608.2488705">10.1145/2488608.2488705</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F88020">1721.1/88020</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-2029-0</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207205207">207205207</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFPintoThiranVetterli2012" class="citation journal cs1">Pinto, P.C.; Thiran, P.; Vetterli, M. (2012). <a rel="nofollow" class="external text" href="http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf">"Locating the source of diffusion in large-scale networks"</a> (PDF). Physical Review Letters. 109 (6): 068702. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1208.2534">1208.2534</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2012PhRvL.109f8702P">2012PhRvL.109f8702P</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevLett.109.068702">10.1103/PhysRevLett.109.068702</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/23006310">23006310</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14526887">14526887</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20121022084454/http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf">Archived</a> (PDF) from the original on 2012-10-22. Retrieved 2012-08-14.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFGeorge_T._HeinemanGary_PolliceStanley_Selkow2008" class="citation book cs1">George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Chapter 8:Network Flow Algorithms". Algorithms in a Nutshell. <a href="Oreilly_Media" class="mw-redirect" title="Oreilly Media">Oreilly Media</a>. pp. 226–250. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-596-51624-6</bdi>.</cite></li>

<li><cite id="CITEREFRavindra_K._AhujaThomas_L._MagnantiJames_B._Orlin1993" class="citation book cs1"><a href="Ravindra_K._Ahuja" title="Ravindra K. Ahuja">Ravindra K. Ahuja</a>; <a href="Thomas_L._Magnanti" title="Thomas L. Magnanti">Thomas L. Magnanti</a>; <a href="James_B._Orlin" title="James B. Orlin">James B. Orlin</a> (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-617549-X</bdi>.</cite></li>

<li><cite id="CITEREFBollobás,_Béla1979" class="citation book cs1"><a href="B%C3%A9la_Bollob%C3%A1s" title="Béla Bollobás">Bollobás, Béla</a> (1979). Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-90399-2</bdi>.</cite></li>

<li><cite id="CITEREFChartrand,_GaryOellermann,_Ortrud_R.1993" class="citation book cs1"><a href="Chartrand%2C_Gary" class="mw-redirect" title="Chartrand, Gary">Chartrand, Gary</a>; <a href="Ortrud_Oellermann" title="Ortrud Oellermann">Oellermann, Ortrud R.</a> (1993). Applied and Algorithmic Graph Theory. New York: McGraw-Hill. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-07-557101-3</bdi>.</cite></li>

<li><cite id="CITEREFEven,_Shimon1979" class="citation book cs1">Even, Shimon (1979). <a rel="nofollow" class="external text" href="https://archive.org/details/graphalgorithms0000even">Graph Algorithms</a>. Rockville, Maryland: Computer Science Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-914894-21-8</bdi>.</cite></li>

<li><cite id="CITEREFGibbons,_Alan1985" class="citation book cs1">Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-28881-9</bdi>.</cite></li>

<li><cite id="CITEREFThomas_H._CormenCharles_E._LeisersonRonald_L._RivestClifford_Stein2001" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>; <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>; <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a> (2001) [1990]. "26". <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a> (2nd ed.). MIT Press and McGraw-Hill. pp. 696–697. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Flow_networks" class="extiw external" title="commons:Category:Flow networks">Flow networks</a>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20080111234829/http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml">Maximum Flow Problem</a></li>

<li><a rel="nofollow" class="external text" href="http://www.dis.uniroma1.it/~challenge9/download.shtml">Real graph instances</a></li>

<li><a rel="nofollow" class="external text" href="http://lemon.cs.elte.hu/">Lemon C++ library with several maximum flow and minimum cost circulation algorithms</a></li>

<li><a rel="nofollow" class="external text" href="http://quickgraph.codeplex.com/">QuickGraph</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180121140629/http://quickgraph.codeplex.com/">Archived</a> 2018-01-21 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, graph data structures and algorithms for .Net</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-17" href="https://en.wikipedia.org/wiki/?title=Flow_network&oldid=1300952579">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>